#ifndef GRAPH_H
#define GRAPH_H
#include <list>
#include <queue>
#include <iostream>
#include <QString>
#include <fstream>
#include <QListIterator>
#include <QDebug>
#include <QMessageBox>
#include <QLinkedList>
using namespace std;
const double MAXCOST = 10000;
const double MAX=10000.0;
template<class T>
class Graph
{

    struct EdgeNode
        {
            int dest;  // 边的终点下标
            double length; // 距离
            double time; // 时间
            double cost; // 花费
            QString sid;// 车次/航班
            operator int(){return dest;}
        };
    T* VA;// 结点数组指针
    list<EdgeNode>* HL;// 邻接表
    int sizeV,sizeE,maxV;// 顶点个数和边的个数
public:
    double GetCost(int si,int dj)const;
    double GetTime(int si,int dj)const;
    double GetLength(int si,int dj)const;//按始点和终点下标读取边的权


    Graph(){sizeV=0;sizeE=0;maxV=100; HL = new list<EdgeNode>[100];VA = new T[100];};
    /*Graph(int n=100):sizeV(0),sizeE(0),maxV(n)
            {
                HL = new list<EdgeNode>[n];
                VA = new T[n];
            }*/
    ~Graph(){delete []VA;delete []HL;}
    int Empty()const{return (sizeV==0);}
    int Full()const{return (sizeV==maxV);}
    int SizeV()const{return sizeV;}
    int SizeE()const{return sizeE;}
    int MaxV()const{return maxV;}
    double GetCost(const T& v1,const T& v2)const;
    double GetTime(const T& v1,const T& v2)const;
    double GetLength(const T& v1,const T& v2)const;
    int FindNode(const T v)const;
    bool FindNode(T v,int pos)const;
    void InsertV(const T v);
    void InsertV(const T v1,const T v2);
    void InsertE(const T v1,const T v2,const double w,const double time,const double length,const QString sid);
    void DeleteV(const T v);
    void DeleteV(const T v1,const T v2);
    void DeleteE(const T v1,const T v2);
    void ReadGraph(const char* filename);
    void WriteGraph(const char* filename);
    void show();
    void djst_traintime(const T v1,const T v2,QString &city,QString &ssid);// 火车最短时间
    void djst_cost(const T v1,const T v2,QString &city,QString &ssid);// 最少消费
    void djst_planetime(const T v1,const T v2,QString &city,QString &ssid);// 飞机最短时间
    //friend istream& operator>>(istream& istr,Graph<T>& g);

};

template<class T>
void Graph<T>::djst_traintime(const T v1,const T v2,QString &city,QString &ssid)// 火车最短时间
{
    /*if(FindNode(v1)==0||FindNode(v2)==0)
    {
        QMessageBox::critical(nullptr,"failed!","输入有误，请检查后重新输入!");
        return ;
    }*/
    //double cost=0;
    int *path=new int[sizeV];// 当前城市前驱
    bool *visit=new bool[sizeV];// 表示是否收录到候选点集
    double *dist=new double[sizeV];
    double *cost=new double[sizeV];

    QString sum_id=QString("将要乘坐的车次为:");
    for(int i=0;i<sizeV;i++){
        path[i] = -1;
        visit[i] = false;
        dist[i] = MAX;
        cost[i] = MAX;
    }

    int start=FindNode(v1);
    //cout<<start<<endl;
    //cout<<sizeV<<endl;
    dist[start] = 0;
    cost[start] = 0;
    int pos=0;//标志循环结束即所有顶点皆被标记
    while(pos!=sizeV)
    {

        double min = MAX;
        int minindex = -1;
        for(int i = 0;i < sizeV; i++)
        {
            if(visit[i] == false && dist[i] < min )
            {
                min = dist[i];
                minindex = i;
            }
        }
        visit[minindex] = true;
        typename list<Graph<T>::EdgeNode>::iterator first=HL[minindex].begin(),last=HL[minindex].end();
        int k=1;
        for(;first!=last;++first)// 对边的遍历
        {
            int dest = first->dest;

            if(visit[dest] == false && dist[minindex] + first->time < dist[dest])
            {
                cost[dest] = cost[minindex] + first->cost;
                dist[dest] = dist[minindex] + first->time;
                path[dest] = minindex;
                sum_id=sum_id+first->sid+";";
                if(k%3==0)
                    sum_id=sum_id+"\n ";
                k++;
            }
        }
        pos++;
    }

    list<T> L;// 结果列表
    list<QString> sid;
    int j=FindNode(v2);
    double count=0;
    qDebug()<<dist[j]<<endl;
    qDebug()<<cost[j]<<endl;

    while(j != -1){
        L.push_front(VA[j]);
        count++;
        j = path[j];
    }
    double num=dist[j]+((count-1)*1);
    qDebug()<<num<<endl;
    QString *t=new QString[L.size()];
    QString sum=QString("火车路程所需最短时间为'%0';\n此时所需开销为:'%1'\n将要经历的城市为:").arg(dist[j]).arg(cost[j]);

     typename list<T>::iterator first=L.begin(),last=L.end();
     for(int i=0;first !=last ;++first,++i)
     {
        t[i]=*first;
        qDebug()<<*first<<" ";
     }
     int s=1;
     for(int i=0;i<L.size();++i,++s)
     {
         sum=sum+t[i]+";";
         if(s%3==0)
             sum=sum+"\n";
     }
     city=sum;
     ssid=sum_id;
     qDebug()<<sum;
     qDebug()<<sum_id;
     //qDebug()<<"总时间:"<<num;
}

template<class T>
void Graph<T>::djst_planetime(const T v1,const T v2,QString &city,QString &ssid)// 航班最短时间
{
    /*if(FindNode(v1)==0||FindNode(v2)==0)
    {
        QMessageBox::critical(nullptr,"failed!","输入有误，请检查后重新输入!");
        return ;
    }*/
    double *cost=new double[sizeV];

    int *path=new int[sizeV];// 当前城市前驱
    bool *visit=new bool[sizeV];// 表示是否收录到候选点集
    double *dist=new double[sizeV];
    QString sum_id=QString("将要乘坐的车次为:");
    for(int i=0;i<sizeV;i++){
        path[i] = -1;
    }
    for(int i=0;i<sizeV;i++){
        visit[i] = false;
    }
    for(int i=0;i<sizeV;i++){
        dist[i] = MAX;
        cost[i] = MAX;
    }
    int start=FindNode(v1);
    //cout<<start<<endl;
    //cout<<sizeV<<endl;
    dist[start] = 0;
    cost[start] = 0;
    int pos=0;//标志循环结束即所有顶点皆被标记
    while(pos!=sizeV)
    {

        double min = MAX;
        int minindex = -1;
        for(int i = 0;i < sizeV; i++)
        {
            if(visit[i] == false && dist[i] < min )
            {
                min = dist[i];
                minindex = i;
            }
        }
        visit[minindex] = true;
        typename list<Graph<T>::EdgeNode>::iterator first=HL[minindex].begin(),last=HL[minindex].end();
        int k=1;
        for(;first!=last;++first)// 对边的遍历
        {
            int dest = first->dest;
            if(visit[dest] == false && dist[minindex] + first->time < dist[dest])
            {
                cost[dest] = cost[minindex] + first->cost;
                dist[dest] = dist[minindex] + first->time;
                path[dest] = minindex;
                sum_id=sum_id+first->sid+";";
                if(k%3==0)
                    sum_id=sum_id+"\n ";
                k++;
            }
        }
        pos++;
    }

    list<T> L;// 结果列表
    list<QString> sid;
    int j=FindNode(v2);
    double count=0;
    qDebug()<<dist[j]<<endl;
    qDebug()<<cost[j]<<endl;
    while(j != -1){
        L.push_front(VA[j]);
        count++;
        j = path[j];
    }
    double num=dist[j]+((count-1)*1);
    qDebug()<<num<<endl;
    QString *t=new QString[L.size()];
    QString sum=QString("飞机路程所需最短时间为'%0';\n此时所需开销为:'%1'\n将要经历的城市为:").arg(dist[j]).arg(cost[j]);

     typename list<T>::iterator first=L.begin(),last=L.end();
     for(int i=0;first !=last ;++first,++i)
     {
        t[i]=*first;
        qDebug()<<*first<<" ";
     }
     int s=1;
     for(int i=0;i<L.size();++i,++s)
     {
         sum=sum+t[i]+";";
         if(s%3==0)
             sum=sum+"\n";
     }
     city=sum;
     ssid=sum_id;
     qDebug()<<sum;
     qDebug()<<sum_id;
     //qDebug()<<"总时间:"<<num;
}

template<class T>
void Graph<T>::djst_cost(const T v1,const T v2,QString &city,QString &ssid)// 最少开销
{
    /*if(FindNode(v1)==0||FindNode(v2)==0)
    {
        QMessageBox::critical(nullptr,tr("failed!"),tr("输入有误，请检查后重新输入!"));
        return ;
    }*/
    double *time=new double[sizeV];
    int *path=new int[sizeV];// 当前城市前驱
    bool *visit=new bool[sizeV];// 表示是否收录到候选点集
    double *dist=new double[sizeV];
    QString sum_id=QString("将要乘坐的车次为:");
    for(int i=0;i<sizeV;i++){
        path[i] = -1;
    }
    for(int i=0;i<sizeV;i++){
        visit[i] = false;
    }
    for(int i=0;i<sizeV;i++){
        dist[i] = MAX;
        time[i] = MAX;
    }
    int start=FindNode(v1);
    //cout<<start<<endl;
    //cout<<sizeV<<endl;
    dist[start] = 0;
    time[start] = 0;
    int pos=0;//标志循环结束即所有顶点皆被标记
    while(pos!=sizeV)
    {
        double min = MAX;
        int minindex = -1;
        for(int i = 0;i < sizeV; i++)
        {
            if(visit[i] == false && dist[i] < min )
            {
                min = dist[i];
                minindex = i;
            }
        }
        visit[minindex] = true;
        typename list<Graph<T>::EdgeNode>::iterator first=HL[minindex].begin(),last=HL[minindex].end();
        int k=1;
        for(;first!=last;++first)// 对边的遍历
        {
            int dest = first->dest;
            if(visit[dest] == false && dist[minindex] + first->cost < dist[dest])
            {
                time[dest] = time[minindex] + first->cost;
                dist[dest] = dist[minindex] + first->cost;
                path[dest] = minindex;
                sum_id=sum_id+first->sid+";";
                if(k%3==0)
                    sum_id=sum_id+"\n";
            }
        }
        pos++;
    }

    list<T> L;// 结果列表
    list<QString> sid;
    int j=FindNode(v2);
    double count=0;
    qDebug()<<dist[j]<<endl;
    qDebug()<<time[j]<<endl;
    while(j != -1){
        L.push_front(VA[j]);
        count++;
        j = path[j];
    }
    double num=dist[j]+((count-1)*1);
    qDebug()<<num<<endl;
    QString *t=new QString[L.size()];
    QString sum=QString("路程最少开销为'%0';\n此时所需总时间(分):'%1'\n将要经历的城市为:").arg(dist[j]).arg(time[j]);

     typename list<T>::iterator first=L.begin(),last=L.end();
     for(int i=0;first !=last ;++first,++i)
     {
        t[i]=*first;
        qDebug()<<*first<<" ";
     }
     int s=1;
     for(int i=0;i<L.size();++i,++s)
     {
         sum=sum+t[i]+";";
         if(s%3==0)
             sum=sum+"\n";
     }
     city=sum;
     ssid=sum_id;
     qDebug()<<sum;
     qDebug()<<sum_id;
     //qDebug()<<"总:"<<num;
}


template<class T>
int Graph<T>::FindNode(const T v)const
{
    for(int i=0;i<sizeV;i++)
        if(VA[i]==v)
            return i;
    return 0;
}


template<class T>
bool Graph<T>::FindNode(T v,int pos)const
{
    if(pos<0 || pos>=sizeV)
        return 0;
    v=VA[pos];
    return 1;
}



template<class T>
void Graph<T>::ReadGraph(const char* filename)	//从文件中读取图的数据
{
    char str[50];
    int n;
    double w;
    T v1,v2;
    ifstream fin;
    fin.open(filename);	//打开文件filename
    if(!fin)
    {
        cout<<"cannot open "<<filename<<endl;
        exit(1);
    }
    fin>>str>>n;					//读取顶点个数
    for(int i=1;i<=n;++i)			//读取n个顶点，插入顶点数组
    {
        fin>>v1;
        InsertV(v1);
    }
    fin>>str>>n;					//读取边数
    for(int i=1;i<=n;++i)				//读取n条边，插入邻接链表
    {
        fin>>v1>>v2>>w;
        InsertE(v1,v2,w);
    }
}




template<class T>
void Graph<T>::WriteGraph(const char* filename)
{
    ofstream fout;
    fout.open(filename);	//打开文件filename
    if(!fout)
    {
        cout<<"cannot open "<<filename<<endl;
        exit(1);
    }
    for(int i=0;i<sizeV;i++)
    {
        fout<<i<<'-'<<VA[i]<<':';		//输出顶点下标和顶点
        //QListIterator<EdgeNode> first=HL[i].begin(),last=HL[i].end();
        typename list<Graph<T>::EdgeNode>::iterator first=HL[i].begin(),last=HL[i].end();
        for(;first!=last;++first)		//输出以该顶点为始点的边链表
            fout<<'('<<(*first).dest<<','<<(*first).cost<<')'<<' ';
        fout<<endl;
    }
    qDebug()<<"ok!";
}




template<class T>
double Graph<T>::GetCost(int si,int dj)const    //私有函数（内部方法）
{
    if((si-1<0) || (si-1>=sizeV) || (dj<0 )|| (dj>=sizeV) || (si=dj))
    {
        //QMessageBox::warning(this,tr("查找失败"),tr("输入值错误"));
        return 0;
    }
    QListIterator<EdgeNode> first=HL[si-1].begin(),last=HL[si-1].end();
    //list<EdgeNode>::const_iterator first=HL[si].begin();
    //list<EdgeNode>::iterator last=HL[si].end();
    for(;first!=last;++first)
        if((*first).dest==dj)
            return (((*first).cost));
    return 0;
}


template<class T>
double Graph<T>::GetCost(const T& v1,const T& v2)const
{
    return GetCost(FindNode(v1),FindNode(v2));
}


template<class T>
double Graph<T>::GetLength(int si,int dj)const    //私有函数（内部方法）
{
    if((si-1<0) || (si-1>=sizeV) || (dj<0 )|| (dj>=sizeV) || (si=dj))
    {
        //QMessageBox::warning(this,tr("查找失败"),tr("输入值错误"));
        return 0;
    }
    QListIterator<EdgeNode> first=HL[si-1].begin(),last=HL[si-1].end();
    //list<EdgeNode>::const_iterator first=HL[si].begin();
    //list<EdgeNode>::iterator last=HL[si].end();
    for(;first!=last;++first)
        if((*first).dest==dj)
            return (((*first).length));
    return 0;
}


template<class T>
double Graph<T>::GetLength(const T& v1,const T& v2)const
{
    return GetCost(FindNode(v1),FindNode(v2));
}

template<class T>
double Graph<T>::GetTime(int si,int dj)const    //私有函数（内部方法）
{
    if((si-1<0) || (si-1>=sizeV) || (dj<0 )|| (dj>=sizeV) || (si=dj))
    {
        //QMessageBox::warning(this,tr("查找失败"),tr("输入值错误"));
        return 0;
    }
    QListIterator<EdgeNode> first=HL[si-1].begin(),last=HL[si-1].end();
    //list<EdgeNode>::const_iterator first=HL[si].begin();
    //list<EdgeNode>::iterator last=HL[si].end();
    for(;first!=last;++first)
        if((*first).dest==dj)
            return (((*first).time));
    return 0;
}


template<class T>
double Graph<T>::GetTime(const T& v1,const T& v2)const
{
    return GetCost(FindNode(v1),FindNode(v2));
}


template<class T>
void Graph<T>::InsertV(const T v)//插入顶点
{
    if(sizeV==maxV)
    {
        //QMessageBox::critical()
        return ;
    }
    VA[sizeV]=v;	//插入顶点数组
    sizeV++;		//顶点个数加1
    //return 1;
}

template<class T>
void Graph<T>::InsertV(const T v1,const T v2)
{
    if(FindNode(v1)==0)
        InsertV(v1);
    if(FindNode(v2)==0)
        InsertV(v2);
}
template<class T>
void Graph<T>::InsertE(const T v1,const T v2,const double cost,const double time,const double length,const QString sid)//插入边
{
    int si=FindNode(v1),dj=FindNode(v2);//确定边的始点和终点的下标
    if(si==-1||dj==-1||si==dj)
        return;
    EdgeNode en;						//边结点数据项
    en.dest=dj;
    en.cost=cost;
    en.length=length;
    en.time=time;
    en.sid=sid;//边结点数据
    HL[si].insert(HL[si].end(),en);		//插入边链表
    sizeE++;
    //return 1;
}

template<class T>
void Graph<T>::DeleteV(const T v)//删除顶点
{
    int si=FindNode(v);
    if(si==-1)
        return;
    int temp=HL[si].size();		//（1）保留被删除边链表的边数
    for(int i=si;i<sizeV-1;i++)
    {
        VA[i]=VA[i+1];		//通过顶点数组元素的复制，删除顶点
        HL[i]=HL[i+1];		//通过边链表数组元素的复制，删除边链表
    }
    HL[sizeV-1].clear();	//原来在最后位置上的边链表要清空
    sizeV--;				//顶点数减1
    sizeE=sizeE-temp;		//减去以删除顶点为始点的边数，即减去删除的边链表长度
    //QListIterator<EdgeNode> first,last;
    typename list<EdgeNode>::iterator first,last; //（2）
    for(int i=0;i<sizeV;i++)				//扫描所有剩余的边链表
    {
        first=HL[i].begin(),last=HL[i].end();
        for(;first!=last;++first)
            if((*first).dest==si)
            {
                HL[i].erase(first);		//删除边结点
                sizeE--;				//边数减1
                break;
            }
    }
    for(int i=0;i<sizeV;i++)	//(3)
    {
        first=HL[i].begin(),last=HL[i].end();
        for(;first!=last;++first)
            if((*first).dest>si)	//要修改的边结点，其数据项dest要大于删除的顶点下标
                (*first).dest--;	//其数据项dest减1
    }
   // return 1;
}
template<class T>
void Graph<T>::DeleteV(const T v1,const T v2)
{
    if(FindNode(v1)!=0)
        DeleteV(v1);
    if(FindNode(v2)!=0)
        DeleteV(v2);
}
template<class T>
void Graph<T>::DeleteE(const T v1,const T v2)//删除边
{
    int si=FindNode(v1),dj=FindNode(v2);//确定边的始点和终点下标
    if(si==-1||dj==-1||si==dj)
        return;
    //QListIterator<EdgeNode> first=HL[si].begin(),last=HL[si].end();
    typename list<EdgeNode>::iterator first=HL[si].begin(),last=HL[si].end();
    for(;first!=last;++first)	//扫描始点所在的边链表
        if((*first).dest==dj)	//找到终点所在的边结点
        {
            HL[si].erase(first);//删除边结点
            sizeE--;			//边数减1
            return;
        }
   // return 0;
}






template<class Iterator>
void Display(Iterator first,Iterator last)
{
    for(;first!=last;++first)
        cout<<*first<<' ';
    cout<<endl;
}

/*
template<class T>
void primDisplay(const Graph<T>& g,PathData E[],int ne)//显示普里姆算法结果
{
    T v1,v2;
    for(int i=ne-1;i>-1;i--)
    {
        g.FindNode(v1,E[i].start);
        g.FindNode(v2,E[i].dest);
        cout<<'('<<v1<<','<<v2<<','<<E[i].cost<<')'<<" ";
    }
    cout<<endl;
}
*/
/*template<class T>
istream& operator>>(istream& istr,Graph<T>& g)
{
    char s[50];
    int n;
    double w;
    T v1,v2;
    istr>>s>>n;
    for(int i=1;i<=n;++i)
    {
        istr>>v1>>v2>>w;
        g.InsertE(v1,v2,w);
    }
    return istr;
}*/

template<class T>
void Graph<T>::show()
{
    for(int i=0;i<this->sizeV;i++)
    {
        qDebug()<<i<<'-'<<this->VA[i]<<':';
        typename list<Graph<T>::EdgeNode>::iterator first=this->HL[i].begin(),last=this->HL[i].end();
        for(;first!=last;++first)
            qDebug()<<'('<<(*first).dest<<','<<(*first).cost<<')'<<' ';
        qDebug()<<endl;
    }
}


#endif
